﻿//Write a program that sorts an array of integers using the merge sort algorithm (find it in Wikipedia).


using System;
using System.Collections.Generic;

public class MergeSortAlgorithm
{
    public static void Main()
    {
        Console.Write("Enter the number of elements of the array: ");
        int length = int.Parse(Console.ReadLine());
        Console.WriteLine("Enter {0} elements of the array", length);
        List<int> array = new List<int>(length);
        for (int i = 0; i < array.Capacity; i++)
        {
            array.Add(int.Parse(Console.ReadLine()));
        }
        Console.WriteLine();
        Console.WriteLine("Array is:");
        for (int i = 0; i < array.Count; i++)
        {
            if (i == 0)
            {
                Console.Write("{{{0}, ", array[i]);
            }
            else if (i == array.Count - 1)
            {
                Console.Write("{0}}}\n", array[i]);
            }
            else
            {
                Console.Write("{0}, ", array[i]);
            }
        }
        List<List<int>> listIntLeft = new List<List<int>>();
        List<List<int>> listIntRight = new List<List<int>>();
        List<int> left = new List<int>();
        List<int> right = new List<int>();
        List<int> result = new List<int>();
        result = MergeSort(array);
        Console.WriteLine("Sorted array is:");
        for (int i = 0; i < result.Count; i++)
        {
            if (i == 0)
            {
                Console.Write("{{{0}, ", result[i]);
            }
            else if (i == result.Count - 1)
            {
                Console.Write("{0}}}\n", result[i]);
            }
            else
            {
                Console.Write("{0}, ", result[i]);
            }
        }
    }

    private static void DevideArray(List<int> list, List<int> left, List<int> right)
    {
        List<int> tempList = list;
        List<int> tempRight = list;
        for (int i = 0; i < list.Count / 2; i++)
        {
            left.Add(list[i]);
            right.Add(list[list.Count / 2 + i]);
        }
    }

    private static List<int> MergeSort(List<int> array)
    {
        List<int> result = new List<int>();
        if (array.Count <= 1)
        {
            return array;
        }
        List<int> left = new List<int>();
        List<int> right = new List<int>();
        int middle = array.Count / 2;
        for (int i = 0; i < middle; i++)
        {
            left.Add(array[i]);
        }
        for (int i = middle; i < array.Count; i++)
        {
            right.Add(array[i]);
        }
        left = MergeSort(left);
        right = MergeSort(right);
        result = Merge(left, right);
        return result;
    }

    private static List<int> Merge(List<int> left, List<int> right)
    {
        List<int> result = new List<int>();

        int i = 0;

        while (left.Count > 0 || right.Count > 0)
        {

            {
                if (left.Count > 0 && right.Count > 0)
                {

                    if (left[i] <= right[i])
                    {
                        result.Add(left[i]);
                        left.RemoveAt(i);
                    }
                    else
                    {
                        result.Add(right[i]);
                        right.RemoveAt(i);
                    }
                }
                else if (left.Count > 0)
                {
                    result.Add(left[i]);
                    left.RemoveAt(i);
                }
                else if (right.Count > 0)
                {
                    result.Add(right[i]);
                    right.RemoveAt(i);
                }
            }
        }
        return result;
    }
}